package com.kehao.newcoder;

import org.junit.Test;

import java.util.Arrays;

public class NC140Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        mySort(arr,0,arr.length-1);
        return arr;
    }

    private void mySort(int[] arr,int start,int end){
        if(start<end){
            if(start==end-1){
                if(arr[start]>arr[end]){
                    swap(arr,start,end);
                }
                return;
            }
            int head= start;
            start++;
            int rear = end;
            while (start<end){
                while (end>head && arr[end]>arr[head]) end--;
                while (start<=rear && arr[start]<arr[head]) start++;
                if(start<end&&end>head&&start<=rear){
                    swap(arr,start,end);
                }
            }
            if(start > rear) {
                start--;
            }
            if(head<end) {
                swap(arr, head, end);
            }
            mySort(arr,head,end-1);
            mySort(arr,end+1,rear);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private void printResult(int[] arr){
        System.out.print("[");
        if(arr!=null) {
            Arrays.stream(arr).forEach(i-> System.out.print(i+","));
            System.out.print("\b]");
        }else {
            System.out.print("]");
        }

    }

    @Test
    public void test01(){
        int[] arr = new int[]{5,2,3,1,4};
        printResult(MySort(arr));
    }
}
